#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->NodeTable = malloc(sizeof(Vertex) * graph->MaxVertex);
	if (graph->NodeTable == NULL)
		return -1;
	for (int i = 0; i < graph->MaxVertex; i++)
		graph->NodeTable[i].adj = NULL;
	return 0;
}
int InsertVertex(Graph *graph, datatype data)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->NodeTable[graph->NumVertex++].data = data;
	return 0;
}
void Show(Graph *graph)
{
	Edge *p;
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%d %c:>", i, graph->NodeTable[i].data);
		p = graph->NodeTable[i].adj;
		while (p != NULL)
		{
			printf("%d--> ", p->dest);
			p = p->link;
		}
		printf("Nul.\n");
	}
}
int GetVertexPosion(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->NodeTable[i].data == vertex)
			return i;
	}
	return -1;
}
int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	// V1-->V2
	Edge *current = malloc(sizeof(Edge));
	if (current == NULL)
		return -2;
	current->dest = p2;
	current->link = graph->NodeTable[p1].adj;
	graph->NodeTable[p1].adj = current;
	++graph->NumEdge;

	return 0;
}
int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	Edge *p = NULL, *q = NULL;
	//删除V1-->V2边
	p = graph->NodeTable[p1].adj;
	while (p != NULL && p->dest != p2)
	{
		q = p;
		p = p->link;
	}
	if (p == NULL)
		return -2;
	if (q == NULL) // p指向的第一个结点就是要找的结点,这时候q还为空
		graph->NodeTable[p1].adj = p->link;
	else
		q->link = p->link;
	free(p);
	--graph->NumEdge;
	return 0;
}
int RemoveVertex(Graph *graph, datatype vertex)
{
	int p1 = GetVertexPosion(graph, vertex);
	if (p1 == -1)
		return -1;
	//删除与结点关联的边
	Edge *pre = NULL, *current, *next;
	current = graph->NodeTable[p1].adj;
	while (current != NULL)
	{
		int p2 = current->dest;
		next = graph->NodeTable[p2].adj;
		while (next->dest != p1)
		{
			pre = next;
			next = next->link;
		}
		if (pre == NULL)
			graph->NodeTable[p2].adj = next->link;
		else
			pre->link = next->link;
		free(next);
		graph->NodeTable[p1].adj = current->link;
		free(current);
		current = graph->NodeTable[p1].adj;
		--graph->NumEdge;
	}
	//删除结点
	--graph->NumVertex;
	graph->NodeTable[p1].data = graph->NodeTable[graph->NumVertex].data;
	graph->NodeTable[p1].adj = graph->NodeTable[graph->NumVertex].adj;
	current = graph->NodeTable[p1].adj;
	while (current != NULL)
	{
		int k = current->dest;
		next = graph->NodeTable[k].adj;
		while (next != NULL)
		{
			if (next->dest == graph->NumVertex)
			{
				next->dest = p1;
				break;
			}
			next = next->link;
		}
		current = current->link;
	}
	return 0;
}
void Destory(Graph *graph)
{
	Edge *p;
	for (int i = 0; i < graph->NumVertex; i++)
	{
		while ((p = graph->NodeTable[i].adj) != NULL)
		{
			graph->NodeTable[i].adj = p->link;
			free(p);
		}
	}
	free(graph->NodeTable);
	graph->NodeTable = NULL;
	graph->NumVertex = graph->NumEdge = 0;
}
int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int p = GetVertexPosion(graph, vertex);
	if (p == -1)
		return -1;
	Edge *current = graph->NodeTable[p].adj;
	if (current != NULL)
		return current->dest;
	return -2;
}
int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	Edge *current = graph->NodeTable[p1].adj;
	while (current != NULL && current->dest != p2)
		current = current->link;
	if (current != NULL && current->link != NULL)
		return current->link->dest;
	return -2;
}

static int *Init_count(Graph *graph, int n)
{
	//初始化保存结点入度的数组
	int *count = malloc(sizeof(int) * n);
	if (count == NULL)
		return NULL;
	for (int i = 0; i < n; i++)
		count[i] = 0;

	//计算各结点的入度并保存到数组中
	for (int i = 0; i < n; i++)
	{
		Edge *p = graph->NodeTable[i].adj;
		while (p != NULL)
		{
			count[p->dest]++;
			p = p->link;
		}
	}

	return count;
}

int TopologicalSort(Graph *graph)
{
	int n = graph->NumVertex;
	int *count = Init_count(graph, n);
	if (count == NULL)
		return -1;

	//模仿入栈过程
	int top = -1;
	for (int i = 0; i < n; i++)
	{
		if (count[i] == 0)
		{
			count[i] = top;
			top = i;
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (top == -1)
			return -2; //没有访问完所有顶点时top等于-1就代表网络中有环
		else
		{
			//结点出栈访问
			int v = top;
			top = count[top];
			printf("%c-->", graph->NodeTable[v].data);

			//求结点的临界顶点并把这些顶点的入度-1
			int w = GetFirstNeighbor(graph, graph->NodeTable[v].data);
			while (w > 0) //这里开始我给的条件是(w != -1),但最后free()总是会报invalid pointer的错误，是没想到GetNextNeighbor还可能有返回值-2，所以当w = -2时便会进入到while循环，然后会操作count[-2]!!!,malloc之后的count指针前面还有一个malloc_chunk结构体，这样程序执行过程中malloc_chunk结构体被破坏，所以最后free()会失败。
			{
				//入度减为0的结点入栈
				count[w]--;
				if (count[w] == 0)
				{
					count[w] = top;
					top = w;
				}
				w = GetNextNeighbor(graph, graph->NodeTable[v].data, graph->NodeTable[w].data);
			}
		}
	}
	printf("Nul.\n");

	free(count);

	return 0;
}

/*
//删除V2-->V1边
p = graph->NodeTable[p2].adj;
q = NULL;
//V1-->V2有边，那么V2-->V1就一定有边,否则这个图的结构就是错误的,所以这里不需要p==NULL的判断
while (p->dest != p1)
{
     q = p;
     p = p->link;
}
if (q == NULL) //p指向的第一个结点就是要找的结点,这时候q还为空
     graph->NodeTable[p2].adj = p->link;
else
     q->link = p->link;
free(p);
*/

/*
//有向无环图无需插入V2-->V1的边
//V2-->V1
current = malloc(sizeof(Edge));
if(current == NULL)
     return -3;
current->dest = p1;
current->link = graph->NodeTable[p2].adj;
graph->NodeTable[p2].adj = current;
*/